package com.rui.study.algorithm.P_动态规划_莱文斯坦距离;

import java.util.Random;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-04 11:05
 **/
public class Solution1回溯法 {

    private char[] a;
    private char[] b;

    private int m;
    private int n;

    private int minEdit = Integer.MAX_VALUE;

    public Solution1回溯法(char[] a, char[] b) {
        this.a = a;
        this.b = b;
        this.m = a.length;
        this.n = b.length;
    }

    public void findEdit(int i, int j, int edit) {
        if (i == m || j == n) {
            if (i < m) edit += (m - i);
            if (j < n) edit += (n - j);
            if (edit < minEdit) minEdit = edit;
            return;
        }

        if (a[i] == b[j]) {
            findEdit(i+1, j+1, edit);   // 两个字符匹配时，编辑次数不变
        } else {
            findEdit(i+1, j, edit+1);   // 不匹配时，删除a[i]或者b[j]前面添加一个字符，编辑次数加1
            findEdit(i, j+1, edit+1);   // 不匹配时，删除b[j]或者a[i]前面添加一个字符，编辑次数加1
            findEdit(i+1, j+1, edit+1); // 不匹配时，a[i]和b[j]替换为相同字符，编辑次数加1
        }
    }

    public static void main(String[] args) {
//        char[] a = "mtacnu".toCharArray();
//        char[] b = "mitcmu".toCharArray();
        int len = 14, ratio = 4;
        char[] a = new char[len];
        char[] b = new char[len];
        Random r1 = new Random(31);
        Random r2 = new Random(31);
        Random r3 = new Random(7);
        StringBuffer bbuf = new StringBuffer();
        for (int i = 0; i < len; i++) {
            a[i] = (char)(97 + r1.nextInt(26));
            char bc = (char)(97 + r2.nextInt(26));
            if (i % ratio != 0) {
                bbuf.append(bc);
            } else {
                bbuf.append((char)(97 + r3.nextInt(26)));
            }
        }
        b = bbuf.toString().toCharArray();
        System.out.println("a: " + String.valueOf(a));
        System.out.println("b: " + String.valueOf(b));
        Solution1回溯法 solution1回溯法 = new Solution1回溯法(a, b);
        long start = System.currentTimeMillis();
        solution1回溯法.findEdit(0,0,0);
        long end = System.currentTimeMillis();
        System.out.println("最小编辑次数：" + solution1回溯法.minEdit + ", 用时：[" + (end - start) + "ms]");
    }
}
